import collections
from typing import List

"""
字母异位词分组
 <a href="https://leetcode.cn/problems/group-anagrams/?envType=study-plan-v2&envId=top-100-liked">leetcode</a>
"""
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        dic = {}
        for s in strs:
            key = "".join(sorted(s))
            if key in dic:
                dic[key].append(s)
            else:
                dic[key] = [s]
        return list(dic.values())

    def groupAnagrams2(self, strs: List[str]) -> List[List[str]]:
        mp = collections.defaultdict(list)
        for st in strs:
            key = "".join(sorted(st))
            mp[key].append(st)

        return list(mp.values())


if __name__ == '__main__':
    s = Solution()
    print(s.groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))
    print(s.groupAnagrams2(["eat", "tea", "tan", "ate", "nat", "bat"]))
